package cm.unit4.theme3;

import java.util.ArrayList;
import java.util.List;

public class VerifySquenceOfBST {

    public static boolean ans = true;

    public void RecVerifySquenceOfBST02(List<Integer> sequence){
        if (sequence.size() > 1){
            Integer root = sequence.get(sequence.size()-1);
            int i = 0;

            List<Integer> leftSequence = new ArrayList<>();
            for (; i < sequence.size()-1; i++) {
                if (sequence.get(i)<root){
                    leftSequence.add(sequence.get(i));
                }else{
                    break;
                }

            }

            List<Integer> rightSequence = new ArrayList<>();
            for (; i < sequence.size()-1; i++) {
                if (sequence.get(i)>root){
                    rightSequence.add(sequence.get(i));
                }else{
                    ans = false;
                    return;
                }
            }
            RecVerifySquenceOfBST(leftSequence);
            RecVerifySquenceOfBST(rightSequence);
        }
        return;
    }

    public boolean RecVerifySquenceOfBST(List<Integer> sequence){
        if (sequence==null){
            return false;
        }

        if (sequence.size() > 1){
            Integer root = sequence.get(sequence.size()-1);
            int i = 0;

            List<Integer> leftSequence = new ArrayList<>();
            for (; i < sequence.size()-1; i++) {
                if (sequence.get(i)<root){
                    leftSequence.add(sequence.get(i));
                }else{
                    break;
                }
            }

            List<Integer> rightSequence = new ArrayList<>();
            for (; i < sequence.size()-1; i++) {
                if (sequence.get(i)>root){
                    rightSequence.add(sequence.get(i));
                }else{
                    return false;
                }
            }
            boolean leftRes = RecVerifySquenceOfBST(leftSequence);
            boolean rightRes = RecVerifySquenceOfBST(rightSequence);
            return leftRes && rightRes;
        }
        return false;
    }

    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence==null || sequence.length==0){
            return false;
        }
        ans = true;
        ArrayList<Integer> list = new ArrayList<>();
        for (int i : sequence) {
            list.add(i);
        }
        RecVerifySquenceOfBST(list);

        return ans;
    }

    public static void main(String[] args) {
        int [] sequence = new int[0];
        System.out.println(sequence.length);
    }
}
